The present invention relates to the field of instruction controlled digital computers and specifically to methods and apparatus associated with storage units in data processing systems.
In particular, the present invention involves virtual address translation buffers and eviction of data from a virtual store when its translation is displaced in the translation buffer.
Recent data processing systems have been designed with virtual storage in which different user programs are operable in the system. The programs identify storage locations with logical addresses. The logical addresses are translated dynamically to real addresses during the processing of instructions. Dynamic address translation is particularly important in multi-programming environments since different programs are free to use the same logical addresses. To avoid interference, the system must translate logical addresses, which are not unique, to real addresses which are unique for each executing program.
In order to provide for the uniqueness of the real addresses when non-unique addresses are employed, translation tables which are unique for each program are provided. The translation tables are typically stored in main storage. The accessing of the translation tables in main storage, however, requires a significant amount of time which can degrade system performance. In order to enhance the performance when translations are made, it is desirable to store translated information in high-speed buffers in order to reduce the number of accesses to main storage.
It is common in data processing systems to have a memory hierarchy wherein buffer memories of relatively low capacity, but of relatively high speed, operate in cooperation with main memories of relatively high capacity but of relatively low speed. It is desired that the vast majority of accesses, either to fetch or store information, be from the buffer memory so that the overall access time of the system is enhanced. In order to have the vast majority of accesses come from the relatively fast buffer memory, information is exchanged between the main memory and the buffer memory in accordance with predetermined algorithms.
In virtual storage, multi-programming systems, it is also desirable to store information in the buffer memory to reduce accesses to main store. In addition to real addresses of data and the data itself, the buffer memory stores logical addresses and program identifiers. With this information in the buffer memory, relatively more time consuming accesses to main storage for the same information are avoided.
The efficiency with which a buffer memory works in decreasing the access time of the overall system is dependent on a number of variables. For example, the capacity of the buffer memory, the capacity of the main store, the data transfer rate between stores, the replacement algorithms which determine when transfers between the main store and buffer are made, and the virtual to real address translation methods and apparatus.
In prior art systems, the address space of the buffer memory and the main store has been the real address space. Therefore, each virtual address from a program required address translation in order to access either the buffer or main store.
In a copending application entitled Virtually Addressed Cache, U.S. Pat. No. 4,612,612, with inventors Woffinden, Hanson and Amdahl, assigned to the same assignee as the present invention, a storage system is described which is addressed by virtual addresses. The system includes a translation lookaside buffer (TLB) which stores a correspondence between virtual addresses and real addresses for entries which are in the high speed buffer. This correspondence is normally stored in the mainstore in translation tables. By storing the correspondence between real and virtual addresses in the TLB, the process of doing virtual-to-real translation operates more quickly.
In that system, when real addresses in the translation lookaside buffer have data stored in the data array, the data must be removed before the TLB entry can be used for a new translation. The eviction process for removing the lines of data from the buffer presents a problem. A new request attempting to use a TLB entry already occupied must wait until the eviction of the data already resident in the buffer takes place. This stopping in order to carry out eviction, however, is undesirable in that it delays processing. Furthermore, in the system described in the copending application, the location of the data entries which correspond to the TLB entry are not directly known.
Therefore searching of the tag array for the corresponding addresses is time-consuming and presents an undesired performance penalty if carried out in the foreground.
There is a need for improved buffer memory systems which are particularly suitable for virtual storage and for multi-programming data processing systems. Specifically, there is a need in such systems for memory hierarchies which have improved methods and apparatus for managing data transfers and for increasing the efficiency of operation.